from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []

        if len(s) < len(p):
            return ans

        # 计算s1的字符状态
        stat1 = [0] * 26
        for ch in p:
            stat1[ord(ch) - 97] += 1

        # 初始化滑动窗口
        stat2 = [0] * 26
        for i in range(len(p)):
            stat2[ord(s[i]) - 97] += 1

        if stat1 == stat2:
            ans.append(0)

        # 移动滑动窗口
        for i in range(len(p), len(s)):
            stat2[ord(s[i]) - 97] += 1
            stat2[ord(s[i - len(p)]) - 97] -= 1
            if stat1 == stat2:
                ans.append(i - len(p) + 1)

        return ans


if __name__ == "__main__":
    print(Solution().findAnagrams(s="cbaebabacd", p="abc"))  # [0,6]
    print(Solution().findAnagrams(s="abab", p="ab"))  # [0,1,2]
